//题目:
// 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。
// 给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
// 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
// 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。
// 如果不可能完成所有课程，返回 一个空数组 。
#include<iostream>
#include<queue>
#include<unordered_map>
#include<vector>

using namespace std;
//代码:
class Solution 
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        //1.用一个哈希表来存放“课程”和“先修课程”的关系
        unordered_map<int,vector<int>> hash;
        for(int i=0;i<prerequisites.size();i++)
            hash[prerequisites[i][1]].push_back(prerequisites[i][0]);
        
        //2.计算所有课程的先修课程门数（入度） prerequisites[i][1]——>prerequisites[i][0]
        vector<int> count(numCourses);
        for(int i=0;i<prerequisites.size();i++)
            count[prerequisites[i][0]]++;
        
        //3.BFS进行拓扑排序
        queue<int> q;
        vector<int> v;
        //a.将所有入度为0的课程入队列
        for(int i=0;i<numCourses;i++)if(count[i]==0)q.push(i);
        //b.BFS
        while(!q.empty())
        {
            //出队列
            int course=q.front();q.pop();
            //擦拭关联线，并判断入队列
            for(auto& x:hash[course]) if(--count[x]==0)q.push(x);
            //记录结果
            v.push_back(course);
        }
        if(v.size()==numCourses)return v;
        return {};
    }
};